/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package com.gemom.auction;

import com.gemom.*;

import java.util.*;
/**
 *
 * @author Yair Diaz
 */


public class searchTree2{
	
        private int numbernodesExplored=0;
        private Vector<Item> fixedItemVector;
	BidNode sroot;	
	int M = 1;
	int B=0;
	int A=3;
	int []stopMask;
	int []prevsm;
	Bid btroot;
	private double total1=0;//will hold the max revenue path value
        private double heuPercent=1.0;

	private Vector<Bid> provpath= new Vector<Bid>();
	private Vector<Bid> currpath=provpath;//will hold the winner path
					   
	double heu=0;
	double g=0;
	double f=0;
	double f_limit=0;
	
	Vector<Vector<Bid>> hFsets;
	Vector<Double> hF;
	
							   
    public searchTree2(Vector<Bid> listBids,double heuPercent){
	
        this.heuPercent=heuPercent;
        //Decoupling itemIDs from labels
        //inside BidGenerator.java
	fixedItemVector =new Vector<Item>();
        for(int i=0;i<listBids.size();i++)
        {   for(int j=0;j<listBids.get(i).getItemsVec().size();j++)
            {  if(!fixedItemVector.contains(listBids.get(i).getItemsVec().get(j)))
                    fixedItemVector.add(listBids.get(i).getItemsVec().get(j));
            }
        }//set the itemflags for each bid
        for(int i=0;i<listBids.size();i++){
        listBids.get(i).setItemflags(fixedItemVector.size(), fixedItemVector);
        }
        
         //Constructing the bid tree
         BidTree bt = new BidTree(listBids);
	 this.btroot= bt.getBidTreeRoot();
        
        //Creating stopMask for pruning the bid tree
	stopMask = new int[fixedItemVector.size()];
	stopMask[0]=M;
	for(int i=1;i<stopMask.length;i++)stopMask[i]=A;
		
	prevsm=new int[fixedItemVector.size()];
	for(int i=0;i<prevsm.length;i++)prevsm[i]=0;
	
        
	//Admissible Heuristic:  
        hFsets= new Vector<Vector<Bid>>();
	for(int i=0;i<fixedItemVector.size();i++)hFsets.add(new Vector<Bid>());
        
        //Vector hF holds h(F) values
	hF = new Vector<Double>();
	
        //each bid is added to the hFset vector where hFset[i]==item_index
     	for(int i=0;i<listBids.size();i++)
            for(int j=0;j<listBids.get(i).getItemflags().length;j++)
                if(listBids.get(i).getItemflags()[j]==1)
                    hFsets.get(j).add(listBids.get(i));

        //generation of h(F) values for each hFset[i] set
	double sum=0;
	for(int i=0;i<hFsets.size();i++)
        {
            for(int j=0;j<hFsets.get(i).size();j++)
		if(sum<(hFsets.get(i).get(j).price)/(hFsets.get(i).get(j).getItemsVec().size()))	
                    sum=(hFsets.get(i).get(j).price)/(hFsets.get(i).get(j).getItemsVec().size());
            hF.add(sum*heuPercent);sum=0;
        }
	

        //Creating root node for searchTree
	sroot = new BidNode(new Bid(88));
	
        //Recursive method: Generation of the searchTree
	searchInOrder(btroot,stopMask,0,sroot,prevsm);//pilas last argument

        //printstree(sroot);

    }//end constructor


    //Recursive method: Generation and exploration of searchTree
    public void searchtree(Bid node, int []stopMask,BidNode bidnode,int[] prevsm){
		
        
     //   System.out.println("hola");
        
        
        numbernodesExplored++;
	
        //adding new node to searchTree
	bidnode.getbch().add(new BidNode(node));
        
        
         if(bidnode.getbch().size()>1)bidnode.getbch().removeElementAt(0);////\/\/\/\/\optimisation
        
	bidnode= bidnode.getbch().lastElement();   
														
	double total=0;
	provpath.clear();
	BidNode bidnode2=sroot.getbch().lastElement();
	Bid aBid=bidnode2.getBid();   
	 
						
	while(!bidnode2.getbch().isEmpty())
        {
            provpath.add(aBid);
            total+=aBid.price;
           
            bidnode2= bidnode2.getbch().lastElement();
            aBid=bidnode2.getBid();
          
            
            if(bidnode2.getbch().isEmpty())
            {
               provpath.add(aBid);
               total+=aBid.price;
            
            }
            
	}//end while
						


//////////////////////////////////////////////////////////////////


        Vector<Bid> listing = new Vector<Bid>();
        Vector<Bid> temp = new Vector<Bid>();
        Bid first;
         while(!provpath.isEmpty())
        {
            first =provpath.firstElement();
            provpath.removeElement(provpath.firstElement());

            for(int i=0;i<provpath.size();i++)
            {
                if(first.getBrokerIdFlag()==provpath.get(i).getBrokerIdFlag())
                    temp.add(provpath.get(i));
            }
            for(int i=0;i<temp.size();i++)provpath.remove(temp.get(i));

            for(int i=0;i<temp.size();i++)
            {
                if(first.price<temp.get(i).price) first=temp.get(i);
            }
            listing.add(first);
             temp.removeAllElements();
         }

         provpath = listing;
         total=0;
         for(int i=0;i<provpath.size();i++)
            {total+=provpath.get(i).price;}



//////////////////////////////////////////////////////////////////////////










	if(total1<total){total1=total;currpath = (Vector<Bid>)provpath.clone();}
	g=total;
	heu=0;
	for(int i=0;i<hF.size();i++)if((prevsm[i]|node.getItemflags()[i])==0)heu+=hF.get(i);
	f= g + heu;	
	heu=0;
	if(f_limit<total1)f_limit=total1;
					
	int[]smclone= stopMask.clone();
	int[]prevsmc= prevsm.clone();
	if(f_limit>f)for(int i=0;i<prevsmc.length;i++)prevsmc[i]=1;
									
/////////////////////////////////////////////////////////////////////////////////////
									
	for(int i=0;i<node.getItemflags().length;i++)prevsmc[i]=prevsmc[i]|node.getItemflags()[i];
	int check=0;
	for(int i=0;i<prevsmc.length;i++)
            {	if(prevsmc[i]==0 && check==0){smclone[i]=M;++check;}
	        else if(prevsmc[i]==0 && check!=0)smclone[i]=A;
	        else if(prevsmc[i]==1)smclone[i]=B;
            }
///////////////////////////////////////////////////////////////////////////////////////////////////////					  
					
					
	searchInOrder(btroot,smclone,0,bidnode,prevsmc);
	
}

public void searchInOrder(Bid node, int []stopMask,int sm, BidNode bidnode,int[] prevsm) {
		
	  if(sm<stopMask.length ){
	  		
	  	if(stopMask[sm]==M){
	  		if(node!=null)node=node.left;
	  		
			if(sm==stopMask.length-1 && node!=null )
					{ //System.out.println(node+"a");
						searchtree(node,stopMask,bidnode,prevsm);
					   }
			searchInOrder(node,stopMask,++sm,bidnode,prevsm);
			
			}
		else if(stopMask[sm]==B ){
			if(node!=null)node=node.right;
						
			if(sm==stopMask.length-1 && node!=null )
					{//System.out.println(node+"b");
					searchtree(node,stopMask,bidnode,prevsm);
					}
			searchInOrder(node,stopMask,++sm,bidnode,prevsm);	
			}
		else if(stopMask[sm]==A){
			Bid v1 = node;
			int sm1 = sm;
			
			if(node!=null)node=node.left;
	  		if(sm==stopMask.length-1 && node!=null)
					{ //System.out.println(node+"c");
					searchtree(node,stopMask,bidnode,prevsm);     }
			searchInOrder(node,stopMask,++sm,bidnode,prevsm);
			
			if(v1!=null)node=v1.right;
			if(sm1==stopMask.length-1 && v1!=null && node!=null)
					{//System.out.println(node+"d");
					searchtree(node,stopMask,bidnode,prevsm);	}
			searchInOrder(node,stopMask,++sm1,bidnode,prevsm);
			
			}
			
	  }//end outer if		
	}//end method

 
  public void printstree(BidNode bidnode){
 	  	  	for(int i=0;i<bidnode.getbch().size();i++){
 				System.out.println(bidnode.getbch().get(i).getBid());
 	 	 			printstree(bidnode.getbch().get(i));}
    		
    
    }//end method
  
  public int getNodesExplored(){return numbernodesExplored;}
  public Vector<Bid>  getWinnerPath(){return currpath;}
  public double getTotalWinnerPath(){return total1;}
  public void setHeuristic(double heuPercent){this.heuPercent=heuPercent;}
  
 
}//end class